package com.le.high.class3;


import org.junit.Test;

/**
 * 给定一个二维数组matrix，每个单元都是一个整数，有正有负。
 * 最开始的时候小Q操纵 一条长度为0的蛇蛇从矩阵最左侧任选一个单元格进入地图，
 * 蛇每次只能够到达当前位 置的右上相邻，右侧相邻和右下相邻的单元格。
 * 蛇蛇到达一个单元格后，自身的长度会 瞬间加上该单元格的数值，
 * 任何情况下长度为负则游戏结束。
 * 小Q是个天才，他拥有一 个超能力，可以在游戏开始的时候把地图中的某一个节点的值变为其相反数（注：最多 只能改变一个节点）。
 * 问在小Q游戏过程中，他的蛇蛇最长长度可以到多少？
 * 比如：
 * 1 -4 10
 * 3 -2 -1
 * 2 -1  0
 * 0  5 -2
 * 最优路径为从最左侧的3开始，3 -> -4(利用能力变成4) -> 10。
 * 所以返回17
 */
public class Problem02_SnakeGame {

    public static int getMaxLength(int[][] matrix) {
        if (matrix == null || matrix[0].length == 0) {
            return -1;
        }
        int res = Integer.MIN_VALUE;
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                Info info = process1(matrix, i, j);
                res = Math.max(res, Math.max(info.no, info.yes));
            }
        }
        return res;
    }

    public static class Info {
        int no; // 不使用超能力最大值
        int yes; // 使用一次超能力的最大值

        public Info(int no, int yes) {
            this.no = no;
            this.yes = yes;
        }
    }

    // 从(i,j)出发一直走到最右侧的旅程中
    // 0) 在没有使用过能力的情况下，返回路径最大和
    // 1) 在使用过能力的情况下，返回路径最大和
    // 每个位置依赖 左上，左，左下，三个位置
    public static Info process1(int[][] matrix, int i, int j) {
        if (j == 0) {
            return new Info(matrix[i][j], -matrix[i][j]);
        }
        int preNo = -1;
        int preYes = -1;
        // 左上
        if (i > 0) {
            Info leftUp = process1(matrix, i - 1, j - 1);
            if (leftUp.no > -1) {
                preNo = leftUp.no;
            }
            if (leftUp.yes > -1) {
                preYes = leftUp.yes;
            }
        }
        // 左
        Info left = process1(matrix, i, j - 1);
        if (left.no > -1) {
            preNo = Math.max(preNo, left.no);
        }
        if (left.yes > -1) {
            preYes = Math.max(preYes, left.yes);
        }

        // 左下
        if (i < matrix.length - 1) {
            Info leftDown = process1(matrix, i + 1, j - 1);
            if (leftDown.no > -1) {
                preNo = Math.max(preNo, leftDown.no);
            }
            if (leftDown.yes > -1) {
                preYes = Math.max(preYes, leftDown.yes);
            }
        }

        // 当前位置
        int curNo = -1;
        int curYes = -1;
        if (preNo > -1) {
            curNo = preNo + matrix[i][j];
            curYes = preNo + (-matrix[i][j]);
        }
        if (preYes > -1) {
            curYes = Math.max(curYes, preYes + matrix[i][j]);
        }
        return new Info(curNo, curYes);
    }



    // 记忆化搜索
    public static int getMaxLength2(int[][] matrix) {
        if (matrix == null || matrix[0].length == 0) {
            return -1;
        }
        int res = Integer.MIN_VALUE;
        Info[][] dp = new Info[matrix.length][matrix[0].length];
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                Info info = process2(matrix, i, j, dp);
                res = Math.max(res, Math.max(info.no, info.yes));
            }
        }
        return res;
    }

    public static Info process2(int[][] matrix, int i, int j, Info[][] dp) {
        if (dp[i][j] != null) {
            return dp[i][j];
        }
        if (j == 0) {
            dp[i][j] = new Info(matrix[i][j], -matrix[i][j]);
            return dp[i][j];
        }
        int preNo = -1;
        int preYes = -1;
        if (i > 0) {
            Info leftUp = process2(matrix, i - 1, j - 1, dp);
            if (leftUp.no > -1) {
                preNo = leftUp.no;
            }
            if (leftUp.yes > -1) {
                preYes = leftUp.yes;
            }
        }
        Info left = process1(matrix, i, j - 1);
        if (left.no > -1) {
            preNo = Math.max(preNo, left.no);
        }
        if (left.yes > -1) {
            preYes = Math.max(preYes, left.yes);
        }
        if (i < matrix.length - 1) {
            Info leftDown = process2(matrix, i + 1, j - 1, dp);
            if (leftDown.no > -1) {
                preNo = Math.max(preNo, leftDown.no);
            }
            if (leftDown.yes > -1) {
                preYes = Math.max(preYes, leftDown.yes);
            }
        }
        int curNo = -1;
        int curYes = -1;
        if (preNo > -1) {
            curNo = preNo + matrix[i][j];
            curYes = preNo + (-matrix[i][j]);
        }
        if (preYes > -1) {
            curYes = Math.max(curYes, preYes + matrix[i][j]);
        }
        dp[i][j] = new Info(curNo, curYes);
        return dp[i][j];
    }

    @Test
    public void test() {
        int[][] matrix = {
                {1, -4, 10},
                {3, -2, -1},
                {2, -1, 0},
                {0, 5, -2}
        };
        System.out.println(getMaxLength(matrix));
        System.out.println(getMaxLength2(matrix));
    }
}
